package com.hello;

import java.util.*;

public class BFS {
    /**
     * leetcode 200 岛屿数量
     *  * 输入：grid = [
     *      *   ["1","1","1","1","0"],
     *      *   ["1","1","0","1","0"],
     *      *   ["1","1","0","0","0"],
     *      *   ["0","0","0","0","0"]
     *      * ]
     *      * 输出：1
     *      *
     *      * 输入：grid = [
     *      *   ["1","1","0","0","0"],
     *      *   ["1","1","0","0","0"],
     *      *   ["0","0","1","0","0"],
     *      *   ["0","0","0","1","1"]
     *      * ]
     *      * 输出：3
     */
    public int numIslands(char[][] grid){
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1'){
                    bfs(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    private void bfs(char[][] grid, int i, int j){
        Queue<int[]> list = new LinkedList<>();
        list.add(new int[] {i,j});
        while (!list.isEmpty()){
            int[] cur = list.remove();
            i = cur[0]; j = cur[1];
            if (0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1'){
                grid[i][j] = '0';
                list.add(new int[]{i+1,j});
                list.add(new int[]{i,j+1});
                list.add(new int[]{i-1,j});
                list.add(new int[]{i,j-1});
            }
        }
    }

    /**
     * leetcode 1091 二进制矩阵中的最短路径
     * 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
     *
     * 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
     *
     * 路径途经的所有单元格都的值都是 0 。
     * 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
     * 畅通路径的长度 是该路径途经的单元格总数。
     */
    private static int[] X = {0,1,1,1,0,-1,-1,-1};
    private static int[] Y = {1,1,0,-1,-1,-1,0,1};
    private static int m,n;
    public static int shortestPathBinaryMatrix(int[][] grid){
        m = grid.length; n = grid[0].length;
        if (grid[0][0] == 1 || grid[m-1][n-1] == 1) return -1;//出口入口被堵死
        if (m == 1 && grid[0][0] == 0) return 1;
        int[][] v = new int[m][n];
        Queue<int[]> a = new LinkedList<>();
        a.add(new int[]{0,0});
        v[0][0] = 1;
        int step = 1;
        while (!a.isEmpty()){
            int s = a.size();
            for (int i = 0; i < s; i++) {
                int[] temp = a.poll();
                int x = temp[0];
                int y = temp[1];
                for (int j = 0; j < 8; j++) {
                    int x1 = x + X[j];
                    int y1 = y + Y[j];
                    if (x1 >= 0 && x1 < m && y1 < n && y1 >= 0 && grid[x1][y1] == 0 && v[x1][y1] != 1){
                        a.add(new int[]{x1,y1});
                        v[x1][y1] = 1;
                    }
                }
                if (x == m-1 && y == n-1) return step;
            }
            step++;
        }
        return -1;
    }

    /**
     * leetcode 207 课程表
     * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
     *
     * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
     *
     * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
     * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
     * 示例 1：
     *
     * 输入：numCourses = 2, prerequisites = [[1,0]]
     * 输出：true
     * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
     * 示例 2：
     *
     * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
     * 输出：false
     * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int [] indegrees = new int[numCourses];//入度表
        List<List<Integer>> adjacency = new LinkedList<>();//邻接表
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        for (int[] cp : prerequisites){
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0){
                queue.add(i);
            }
        }
        while (!queue.isEmpty()){
            int pre = queue.poll();
            numCourses--;
            for (int cur : adjacency.get(pre)){
                if (--indegrees[cur] == 0) queue.add(cur);
            }
        }
        return numCourses == 0;
    }
}